package List;

/**
 * Created by Administrator on 2017/10/9/009.
 */
public class Sorting {
    public static void selectionSort(int[]data){
        int min;
        for(int index = 0;index<data.length-1;index++){
            min = index;
            for(int scan = index+1;scan<data.length;scan++)
                if(data[scan]<data[min])
                    min = scan;
            swap(data,min,index);

        }
    }
    private static void swap(int[]data,int index1,int index2){
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
    public static void insertionSort (int[] data)
    {
        for (int index = 1; index < data.length; index++)
        {
           int key = data[index];
            int position = index;

            // Shift larger values to the right
            while (position > 0 && data[position-1]>key)
            {
                data[position] = data[position-1];
                position--;
            }

            data[position] = key;
        }
    }
    public static void bubbleSort (int[] data)
    {
        int position, scan;

        for (position = data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
                if (data[scan]>data[scan+1])
                    swap (data, scan, scan+1);
        }
    }
    public static void quickSort(int[]data,int min,int max){
        int pivot;
        if(min<max)
        {
            pivot = partition(data,min,max);
            quickSort(data,min,pivot-1);
            quickSort(data,pivot+1,max);
        }
    }
    private static int partition (int[] data, int min, int max)
    {
        // Use first element as the partition value
        int partitionValue = data[min];

        int left = min;
        int right = max;

        while (left < right)
        {
            // Search for an element that is > the partition element
            while (data[left]<=partitionValue && left < right)
                left++;

            // Search for an element that is < the partitionelement
            while (data[right]>partitionValue)
                right--;

            if (left < right)
                swap(data, left, right);
        }

        // Move the partition element to its final position
        swap (data, min, right);

        return right;
    }
    public static void mergeSort (int[] data, int min, int max)
    {
        if (min < max)
        {
            int mid = (min + max) / 2;
            mergeSort (data, min, mid);
            mergeSort (data, mid+1, max);
            merge (data, min, mid, max);
        }
    }
    public static void merge (int[] data, int first, int mid,
                              int last)
    {
        int[] temp = new int[data.length];

        int first1 = first, last1 = mid;  // endpoints of first subarray
        int first2 = mid+1, last2 = last;  // endpoints of second subarray
        int index = first1;  // next index open in temp array

        //  Copy smaller item from each subarray into temp until one
        //  of the subarrays is exhausted
        while (first1 <= last1 && first2 <= last2)
        {
            if (data[first1]<data[first2])
            {
                temp[index] = data[first1];
                first1++;
            }
            else
            {
                temp[index] = data[first2];
                first2++;
            }
            index++;
        }

        //  Copy remaining elements from first subarray, if any
        while (first1 <= last1)
        {
            temp[index] = data[first1];
            first1++;
            index++;
        }

        //  Copy remaining elements from second subarray, if any
        while (first2 <= last2)
        {
            temp[index] = data[first2];
            first2++;
            index++;
        }

        //  Copy merged data into original array
        for (index = first; index <= last; index++)
            data[index] = temp[index];
    }


}

